package oj_leetcode;

import java.util.HashSet;
import java.util.Set;

public class SolveSudoku {

    public static void main(String[] args) {
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {
                '.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {
                '4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {
                '.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {
                '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        new SolveSudoku().solveSudoku(board);
    }

    public void solveSudoku(char[][] board) {
        // 找第一个需要填入的坐标
        int nextR = -1, nextC = -1;
        label:
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    nextR = r;
                    nextC = c;
                    break label;
                }
            }
        }
        Set<Character>[] rowSets = new HashSet[9];
        Set<Character>[] columnSets = new HashSet[9];
        Set<Character>[] threeSets = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rowSets[i] = new HashSet<>();
            columnSets[i] = new HashSet<>();
            threeSets[i] = new HashSet<>();
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // 锁定3*3的块
                for (int r = 0; r < 3; r++) {
                    for (int c = 0; c < 3; c++) {
                        // 锁定块中的数
                        int rowSetIndex = i * 3 + r;
                        int columnSetIndex = j * 3 + c;
                        int threeSetIndex = i * 3 + j;
                        // 判断是否为.
                        if (board[rowSetIndex][columnSetIndex] == '.') {
                            continue;
                        }

                        // 判断有没有该行
                        Set<Character> rowSet = rowSets[rowSetIndex];
                        // 判断该行中是否存在该数
                        rowSet.add(board[rowSetIndex][columnSetIndex]);

                        // 判断有没有该列
                        Set<Character> columnSet = columnSets[columnSetIndex];
                        // 判断该行中是否存在该数
                        columnSet.add(board[rowSetIndex][columnSetIndex]);

                        // 判断3*3
                        Set<Character> threeSet = threeSets[threeSetIndex];
                        // 判断3*3有没有该数
                        threeSet.add(board[rowSetIndex][columnSetIndex]);
                    }
                }
            }
        }
        if (nextR != -1) {
            traceback(board, nextR, nextC, rowSets, columnSets, threeSets);
        }
    }

    public boolean traceback(char[][] board, int row, int column, Set<Character>[] rowSets, Set<Character>[] columnSets, Set<Character>[] boxSets) {
        int boxIndex = row / 3 * 3 + column / 3;
        Set<Character> rs = rowSets[row];
        Set<Character> cs = columnSets[column];
        Set<Character> bs = boxSets[boxIndex];

        // 确定可能值
        Set<Character> exist = new HashSet<>();
        exist.addAll(rs);
        exist.addAll(cs);
        exist.addAll(bs);

        if (exist.size() == 9) {
            return false;
        }
        // 确定下一个位置
        int nextR = -1, nextC = -1;
        label2:
        for (int r = row; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (r == row && c == 0) {
                    c = column + 1;
                    if (c == 9) {
                        r++;
                        c = 0;
                        if (r == 9){
                            break label2;
                        }
                    }
                }
                if (board[r][c] == '.') {
                    nextR = r;
                    nextC = c;
                    break label2;
                }
            }
        }

        // 进行递归/返回
        for (char i = '1'; i <= '9'; i++) {
            if (!exist.contains(i)) {
                board[row][column] = i;
                Set<Character>[] currRSs = rowSets.clone();
                Set<Character>[] currCSs = columnSets.clone();
                Set<Character>[] currBSs = boxSets.clone();
                Set<Character> currRS = new HashSet(rs);
                Set<Character> currCS = new HashSet(cs);
                Set<Character> currBS = new HashSet(bs);
                currRS.add(i);
                currCS.add(i);
                currBS.add(i);
                currRSs[row] = currRS;
                currCSs[column] = currCS;
                currBSs[boxIndex] = currBS;
                if (nextR == -1 && nextC == -1) {
                    return true;
                } else {
                    if (traceback(board, nextR, nextC, currRSs, currCSs, currBSs)) {
                        return true;
                    }
                }
                board[row][column] = '.';
            }
        }
        return false;
    }


}
